package acm.华中农业;
// package niuke.edu.huazhongkejidaxue;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class J2 {

    static long ksm(long b, long v, long mod) {
        long r = 1l;
        while (v > 0) {
            if (v % 2 == 1) {
                r = r * b % mod;
            }
            v /= 2;
            b = b * b % mod;
        }
        return r;
    }

    public static void main(String[] args) {
        long mod = (long)1e9;
        int MN = 5 * 100_0000 + 1;

        int[] cnt2  = new int[MN];
        int[] cnt5 = new int[MN];
        long[] fac = new long[MN];
        fac[0] = fac[1] = 1;
        for (int i = 2; i < MN; i++) {
            int v = i;
            cnt2[i] = cnt2[i - 1];
            cnt5[i] = cnt5[i - 1];
            while (v % 2 == 0) { v /= 2; cnt2[i]++; }
            while (v % 5 == 0) { v /= 5; cnt5[i]++; }
            fac[i] = fac[i - 1] * v % mod;
        }

        long[] dp = new long[MN];
        dp[0] = 1;
        long[] g2 = new long[MN];
        long[] g5 = new long[MN];
        for (int i = 1; i < MN; i++) {
            g2[i] = g2[i - 1] + cnt2[i];
            g5[i] = g5[i - 1] + cnt5[i];
            dp[i] = dp[i - 1] * fac[i] % mod;
        }

        AReader sc = new AReader();
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt(), k = sc.nextInt();
            long p = (long)Math.pow(10, k);

            long d = g2[n] - g5[n];

            long r = ksm(2, d, mod);
            long left = dp[n] * r % p;

            String str = String.valueOf(left);
            while (str.length() < k) {
                str = "0" + str;
            }
            System.out.println(str);
        }

    }

    static
    class AReader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");
        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }
        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {
                String nextLine = innerNextLine();
                if (nextLine == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);
            }
            return true;
        }
        public String nextLine() {
            tokenizer = new StringTokenizer("");
            return innerNextLine();
        }
        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

//        public BigInteger nextBigInt() {
//            return new BigInteger(next());
//        }
        // 若需要nextDouble等方法，请自行调用Double.parseDouble包装
    }

}
